/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package linkeddata.arida.ufc.br.search;

/**
 *
 * @author jeovane
 */
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class Graph {

    private Node rootNode;
    private ArrayList nodes = new ArrayList();
    private int[][] adjMatrix;//Edges will be represented as adjacency Matrix
    private int size;

    public void setRootNode(Node n) {
        this.rootNode = n;
    }

    public ArrayList getNodes() {
        return nodes;
    }

    public void setNodes(Node nodes) {
        this.nodes.add(nodes);
    }

    //This method will be called to make connect two nodes
    public void connectNode(Node start, Node end) {
        if (adjMatrix == null) {
            size = nodes.size();
            adjMatrix = new int[size][size];
        }

        int startIndex = nodes.indexOf(start);
        int endIndex = nodes.indexOf(end);
        adjMatrix[startIndex][endIndex] = 1;
        adjMatrix[endIndex][startIndex] = 1;
    }

    private Node getUnvisitedChildNode(Node n) {
        int index = nodes.indexOf(n);
        int j = 0;
        while (j < size) {
            if (adjMatrix[index][j] == 1 && ((Node) nodes.get(j)).visited == false) {
                return (Node) nodes.get(j);
            }
            j++;
        }
        return null;
    }

    //BFS traversal of a tree is performed by the bfs() function
    public Set<Node> bfs() {
        Set<Node> clazz = new LinkedHashSet<Node>();
        //BFS uses Queue data structure
        Queue queue = new LinkedList();
        queue.add(this.rootNode);
        clazz.add(this.rootNode);
        rootNode.visited = true;
        while (!queue.isEmpty()) {
            Node n = (Node) queue.remove();
            Node child = null;
            while ((child = getUnvisitedChildNode(n)) != null) {
                child.visited = true;
                clazz.add(child);
                queue.add(child);
            }
        }
        //Clear visited property of nodes
        clearNodes();
        return clazz;
    }

    //DFS traversal of a tree is performed by the dfs() function
    public Set<Node> dfs() {
        Set<Node> clazz = new LinkedHashSet<Node>();
        //DFS uses Stack data structure
        Stack stack = new Stack();
        stack.push(this.rootNode);
        rootNode.visited = true;
        clazz.add(rootNode);
        while (!stack.isEmpty()) {
            Node n = (Node) stack.peek();
            Node child = getUnvisitedChildNode(n);
            if (child != null) {
                child.visited = true;
                stack.push(child);
            } else {
                stack.pop();
            }
        }
        //Clear visited property of nodes
        clearNodes();
        return clazz;
    }

    //Utility methods for clearing visited property of node
    private void clearNodes() {
        int i = 0;
        while (i < size) {
            Node n = (Node) nodes.get(i);
            n.visited = false;
            i++;
        }
    }

    //Utility methods for printing the node's label
    private void printNode(Node n) {
        System.out.print(n.label + " ");
    }
}
